﻿#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

//此结构体供后面OJ题使用
typedef struct ListNode {
	int val;
	struct ListNode* next;
} ListNode;

////203. 移除链表元素 https://leetcode.cn/problems/remove-linked-list-elements/description/
////双指针版本，cur指向当前节点，prev指向cur的前一节点。把cur指向节点等于val的删除
////自己的实现
//struct ListNode* removeElements(struct ListNode* head, int val) {
//	struct ListNode* cur = head;
//	struct ListNode* prev = NULL;
//
//	while (cur != NULL) {
//		// 等于就删除
//		if (cur->val == val) {
//			// 头删
//			if (cur == head && cur->next != NULL) {//非最后节点
//				prev = cur;
//				cur = cur->next;
//				head = cur;
//				free(prev);
//			}
//			else if (cur == head && cur->next == NULL) {//最后节点
//				free(cur);
//				return NULL;
//			}
//			// 非头删
//			else {
//				prev->next = cur->next;
//				free(cur);
//				cur = prev->next;
//			}
//		}
//		// 不等于就向下个节点移动
//		else {
//			prev = cur;
//			cur = cur->next;
//		}
//	}
//	return head;
//}
//
////老师的实现
//struct ListNode* removeElements(struct ListNode* head, int val) {
//	struct ListNode* cur = head;//当前节点指针
//	struct ListNode* prev = NULL;//cur前一节点指针
//
//	while (cur != NULL) {
//		// 等于就删除
//		if (cur->val == val) {
//			// 头删
//			if (prev == NULL) {//上一节点指针为空，说明cur指向了头节点
//				cur = head->next;//cur移动到头节点的下一节点
//				free(head);//释放当前头节点
//				head = cur;//头节点移动到cur处（即下一节点）
//			}
//			// 非头删
//			else {
//				prev->next = cur->next;//因为要删除cur指向的节点，所以prev指向的前一节点的指针域要指向cur后面的节点
//				free(cur);//释放cur节点
//				cur = prev->next;//cur移动到prev的下一节点
//			}
//		}
//		// 不等于就向下个节点移动
//		else {
//			prev = cur;//cur移动前先赋值给prev指针
//			cur = cur->next;
//		}
//	}
//	return head;
//}
//
////遍历当前链表，把不是val的拿下来尾插
//struct ListNode* removeElements(struct ListNode* head, int val) {
//    struct ListNode* cur = head;//遍历原链表的指针
//    struct ListNode* newhead = NULL;//新链表头节点指针
//    struct ListNode* tail = NULL;//新链表尾指针
//
//    while (cur)
//    {
//        if (cur->val != val) //不等于val
//        {
//            if (tail == NULL)//新链表为空
//                newhead = tail = cur;//新链表头尾结点指针同时指向第一个不等于val的节点
//            else //新链表不为空
//            {
//                tail->next = cur;//链接下一个不等于val的节点
//                tail = tail->next;//尾指针移动到下一节点，即新链表最后节点
//            }
//            cur = cur->next;//原链表指针移动到下一节点
//            tail->next = NULL;//尾指针的next置为空
//        }
//        else //等于val
//        {
//            struct ListNode* del = cur;//删除当前节点
//            cur = cur->next;//cur移动到下一节点
//            free(del);
//        }
//    }
//    return newhead;
//}



////876. 链表的中间结点 https://leetcode.cn/problems/middle-of-the-linked-list/description/
////版本一：遍历链表，查看有几个节点，再找中间节点
//struct ListNode* middleNode(struct ListNode* head) {
//	struct ListNode* tail = head;
//	int n = 1;
//	while (tail->next != NULL) {
//		tail = tail->next;
//		n++;
//	}
//
//	n = (n / 2) + 1;
//	tail = head;
//	while (--n)//tail已经指向第一节点（而不是空），所以要--n
//		tail = tail->next;
//
//	return tail;
//}
//
//// 版本二：快慢指针，慢指针一次一步，快指针一次两步。
//// 当快指针遍历完链表，慢指针指向的位置是快指针的一半
//struct ListNode* middleNode(struct ListNode* head) {
//	struct ListNode* slow = head;
//	struct ListNode* fast = head;
//	// 老师方法
//	// fast为空，说明fast指向最后一个节点的后面
//	// fast->next为空，说明fast指向最后一个节点
//	// 以上两种情况fast都遍历完链表，循环停下
//	while (fast && fast->next) {
//		slow = slow->next;
//		fast = fast->next->next;
//	}
//
//	// // 自己的方法
//	// while (fast->next) {
//	//     slow = slow->next;
//	//     if (fast->next->next == NULL)
//	//         return slow;
//	//     fast = fast->next->next;
//	// }
//	return slow;
//}



////HJ51 输出单向链表中倒数第k个结点 https://www.nowcoder.com/practice/54404a78aec1435a81150f15f899417d?tpId=37&tqId=21274&ru=/exam/oj
////牛客网
////思路：
////设置快慢指针，并同时指向头结点。
////假设找倒数第4个，那么让，快指针走4步，在让快慢指针同时走一步，慢指针指向的就是倒数第4个
////注意：此方法快指针最后指向尾结点的后面，如果要让快指针指向最后节点，那么走k-1步
//
//typedef struct List_Node {
//    int data;
//    struct List_Node* next;
//} List_Node;
//
//int main() {
//    int len = 0;//链表节点个数
//
//    while (scanf("%d", &len) != EOF) {
//        List_Node* head = NULL;//链表头节点指针
//        List_Node* tail = NULL;//链表尾指针
//
//        for (int i = 0; i < len; i++) {//尾插节点
//            List_Node* newnode = (List_Node*)malloc(sizeof(ListNode));
//            scanf("%d", &(newnode->data));
//            newnode->next = NULL;
//
//            if (head == NULL) {//第一次空链表，head指向空
//                head = newnode;//让head指针指向新节点（此新节点为头节点）
//                tail = head;//tail指向头节点
//            }
//            else {
//                tail->next = newnode;//链接新节点（新节点指针存放到tail节点的指针域）
//                tail = tail->next;//tail指针向下一节点移动
//            }
//        }
//
//        int k = 0;//倒数第几个
//        scanf("%d", &k);
//        List_Node* slow = head;//慢指针
//        List_Node* fast = head;//快指针
//        while (k--)//让fast走k步
//            fast = fast->next;
//
//        //让fast和slow同时向后走一步，当fast指向空（即最后节点的后面）才停下
//        while (fast != NULL) {
//            fast = fast->next;
//            slow = slow->next;
//        }
//
//        printf("%d\n", slow->data);
//    }
//    return 0;
//}
//
////返回倒数第 k 个节点   https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/description/
////leetcode
//int kthToLast(struct ListNode* head, int k) {
//    int kthToLast(struct ListNode* head, int k) {
//        struct ListNode* slow = head;
//        struct ListNode* fast = head;
//
//        //fast走k步版本
//        while (k--)
//        {
//            if (fast == NULL)
//                return NULL;
//
//            fast = fast->next;
//        }
//
//        while (fast)
//        {
//            slow = slow->next;
//            fast = fast->next;
//        }
//        return slow->val;
//        
//
//    //    //fast走k-1步版本
//    //    k = k - 1;
//    //    while (k--)
//    //    {
//    //        if (fast == NULL)
//    //            return NULL;
//
//    //        fast = fast->next;
//    //    }
//
//    //    while (fast->next)
//    //    {
//    //        slow = slow->next;
//    //        fast = fast->next;
//    //    }
//    //    return slow->val;
//    //}
//}



////206. 反转链表  https://leetcode.cn/problems/reverse-linked-list/description/
////给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
////示例 1：
////输入：head = [1, 2, 3, 4, 5]
////输出：[5, 4, 3, 2, 1]
////
////示例 2：
////输入：head = [1, 2]
////输出：[2, 1]
////
////示例 3：
////输入：head = []
////输出：[]
//
//// 遍历原链表，挨个取出头插到新链表（头插不需要判断链表是否为空，尾插才需要）
////自己方法
//struct ListNode* reverseList(struct ListNode* head) {
//	struct ListNode* tail = head;     // head链表尾指针
//	struct ListNode* new_head = NULL; // new_head链表头节点指针
//	struct ListNode* cur = NULL;      // new_head链表当前节点指针
//
//	while (tail) {
//		if (new_head == NULL) // 此时new_head是空链表，插入第一个节点
//		{
//			new_head = cur = head;//让new_head和cur指向原链表第一个节点
//
//			// 下方这里提前移动为了记录下一节点的指针，
//			// 防止后续链接新链表时丢失原链表的位置。
//			// 因为本质上没有复制链表，只是改动原链表各节点指针域的指针
//			head = head->next;//head移动到下一节点
//			tail = head;//tail指向head指向的节点
//			cur->next = NULL;//原链表的第一个节点是新链表最后一个节点，所以置为空
//		}
//		else {
//			tail = tail->next;//tail移动到下一节点，当前节点有head指针维护
//			new_head = head;//到这里时，head已经向后移动了一步，也就是指向第2节点
//			new_head->next = cur;//cur指向的还是原链表的第一节点
//			cur = new_head;//cur移到到new_head位置，用来记录新链表的头，以便下次链接
//			head = tail;//head移动到tail的位置，下次循环进来，tail会先向后移动
//		}
//	}
//	return new_head;
//}
//
//// 按老师思路 - 自己的实现
//struct ListNode* reverseList(struct ListNode* head) {
//	if (head == NULL)
//		return NULL;
//
//	struct ListNode* cur = head;//cur指向目前要头插的节点
//	struct ListNode* next = cur->next;//next指向cur后一节点
//	struct ListNode* rhead = NULL;//新的头节点
//
//	while (cur) {
//		//这里不需要判断rhead是否为空，第一次插入时需要第一个节点指向空。
//		//rhead恰好为空。后续插入都需要让新节点指向原先的头节点
//		cur->next = rhead;
//		rhead = cur;//移动新链表头节点
//		cur = next;//cur向后移动一步
//		if (next)
//			//next向后移动一步，注意如果next为空，
//			//那么下方next->next就会造成对空指针解引用，所以加限制条件
//			next = next->next;
//	}
//	return rhead;
//}
//
//// 老师实现（优化上方）
//struct ListNode* reverseList(struct ListNode* head) {
//	struct ListNode* cur = head;//cur指向目前要头插的节点
//	struct ListNode* rhead = NULL;//新的头节点
//
//	while (cur)
//	{
//		struct ListNode* next = cur->next;//next指向cur后一节点
//
//		//头插
//		cur->next = rhead;//cur指向的当前节点的指针域要指向新链表头结点，即头插
//		rhead = cur;//头节点移动到新节点
//		//迭代
//		cur = next;//当前指向后移动
//	}
//	return rhead;
//}
//
//// 迭代：遍历原链表并改动原链表节点指针域的指向（此版本变量混乱）
//struct ListNode* reverseList(struct ListNode* head) {
//	struct ListNode* tail = head;// head链表尾指针
//	struct ListNode* new_head = NULL;// new_head链表头节点指针
//	struct ListNode* cur = NULL;// new_head链表当前节点指针
//
//	while (tail) {
//		if (new_head == NULL) {
//			tail = tail->next;//原链表尾指针先向后移动，记录下个节点的位置
//			new_head = head;//新链表头节点指针指向原链表第一个节点
//			new_head->next = NULL;//原链表头节点是新链表最后节点，所以指针域置为空
//			cur = new_head;//cur指针先指向先链表头节点，后续用来记录新链表中新节点前的位置
//		}
//		else {
//			head = tail;//原链表头节点移动到tail处（tail已经指向第二节点）
//			tail = tail->next;//tail向后移动，记录下一节点位置
//			new_head = head;//新链表头节点指向原链表下一节点
//			new_head->next = cur;//将新链表链接，cur指向的新链表头节点的前一节点
//			cur = new_head;//cur记录当前新链表头结点，为后续链接做准备			
//		}
//	}
//	return new_head;
//}
//
//// 遍历原链表并改动原链表节点指针域的指向（优化变量名版本）
////自己的实现
//struct ListNode* reverseList(struct ListNode* head) {
//	struct ListNode* n0 = NULL; // 新链表最后节点的指针域
//	struct ListNode* n1 = NULL; // 新链表第一节点
//	struct ListNode* n2 = NULL; // 新链表第二节点
//
//	if (head == NULL)
//		return head;
//
//	// 将n0~01分别指向对应位置
//	n1 = head;
//	n2 = n1->next;
//	n1->next = n0;
//	// 迭代
//	while (n2) {
//		// 三个指针每次向后移动一步
//		n0 = n1;
//		n1 = n2;
//		n2 = n2->next;
//		n1->next = n0;//改变节点链接
//	}
//
//	return n1;
//}
//
////老师的实现，优化上方
//struct ListNode* reverseList(struct ListNode* head) {
//	if (head == NULL)
//		return NULL;
//
//	struct ListNode* n0 = NULL; //n0为最后节点的指针域
//	struct ListNode* n1 = head;      
//	struct ListNode* n2 = n1->next; 
//	
//	//n0和n1用于反转链表，n2用于迭代找到下节点
//	while (n1) {
//		n1->next = n0;
//		// 迭代
//		n0 = n1;
//		n1 = n2;
//		if (n2)
//			n2 = n2->next;
//	}
//	return n0;
//}



////21. 合并两个有序链表
////将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 https://leetcode.cn/problems/merge-two-sorted-lists/description/
////示例 1：
////输入：l1 = [1, 2, 4], l2 = [1, 3, 4]
////输出：[1, 1, 2, 3, 4, 4]
////
////示例 2：
////输入：l1 = [], l2 = []
////输出：[]
////
////示例 3：
////输入：l1 = [], l2 = [0]
////输出：[0]
//
////比较两个链表的节点，取小的尾插
////自己方法
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//    struct ListNode* head = NULL;
//    struct ListNode* tail = NULL;
//    struct ListNode* tmp = NULL;
//
//    //if (list1 == NULL && list2 != NULL)//l1为空，l2不为空
//    //    return list2;
//    //else if (list1 != NULL && list2 == NULL)//l1不为空，l2为空
//    //    return list1;
//    //else if (list1 == NULL && list2 == NULL)//l1和l2都为空
//    //    return NULL;
//
//    //优化上方
//    if (list1 == NULL)//l1为空，l2不为空
//        return list2;
//    else if (list2 == NULL)//l1不为空，l2为空
//        return list1;
//
//    while (list1 && list2) { //l1和l2都不为空
//        if (list1->val < list2->val) { //l1<l2
//            tmp = list1;
//            list1 = list1->next;
//        }
//        else { //l1>l2
//            tmp = list2;
//            list2 = list2->next;
//        }
//
//        if (head == NULL) { // 新链表为空
//            head = tail = tmp;
//        }
//        else { // 新链表不为空
//            tail->next = tmp;
//            tail = tail->next;
//        }
//    }
//
//    if (list1 == NULL) // 说明l1遍历完了
//        tail->next = list2;
//    else if (list2 == NULL)
//        tail->next = list1;
//
//    return head;
//}
//
////老师方法
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//    struct ListNode* head = NULL;
//    struct ListNode* tail = NULL;
//
//    //l1为空，返回l2；l2为空，返回l1
//    if (list1 == NULL)
//        return list2;
//    if (list2 == NULL)
//        return list1;
//
//    //比较两个链表节点大小，取小的尾插
//    while (list1 && list2) { //l1和l2都不为空
//        if (list1->val < list2->val) { //l1<l2
//            if (tail == NULL) //新链表为空
//                head = tail = list1;
//            else { //新链表不为空
//                tail->next = list1;//链接节点
//                tail = tail->next;//tail移动一步
//            }
//            list1 = list1->next;//l1移动一步
//
//        }
//        else { ////l1>=l2
//            if (tail == NULL)  //新链表为空
//                head = tail = list2;
//            else { //新链表不为空
//                tail->next = list2;//链接节点
//                tail = tail->next;//tail移动一步
//            }
//            list2 = list2->next;//l2移动一步
//        }
//    }
//
//    if (list1) //l1不为空
//        tail->next = list1;
//    if (list2) //l2不为空
//        tail->next = list2;
//    return head;//返回新链表头节点指针。（上方条件都不满足就是两个链表都为空，head初始值为空，直接返回空。）
//}
//
////带哨兵位版本
////自己的实现
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//	if (list1 == NULL && list2 == NULL) //两个都为空
//		return NULL;
//
//	struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));//创建哨兵位
//	struct ListNode* tail = guard;//tail指向哨兵位
//	while (list1 && list2) { //两个都不为空
//		if (list1->val < list2->val) { //list1小
//			tail->next = list1;//尾插list1
//			list1 = list1->next;//list1向后移动
//		}
//		else { //list2小
//			tail->next = list2;//尾插list2
//			list2 = list2->next;//list2向后移动
//		}
//		tail = tail->next;//tail向后移动
//	}
//
//	//下方有两个功能：
//	//1. 某一链表为空时，返回另一个链表
//	//2. 上方while循环结束后，有一个链表已尾插完，将剩下另一个链表的节点尾插
//	if (list1 == NULL)
//		tail->next = list2;
//	else if (list2 == NULL)
//		tail->next = list1;
//
//	return guard->next;
//}
//
////老师的实现
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//	struct ListNode* head = NULL;
//	struct ListNode* tail = NULL;
//	//这里创建了一个哨兵位，此时的head和tail还没有指向链表头节点
//	head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
//
//	if (list1 == NULL)
//		return list2;
//	if (list2 == NULL)
//		return list1;
//
//	// 有了哨兵位就不需要判断头节点是否为空，因为增加一个占位节点相当于链表始终不为空
//	while (list1 && list2) {
//		if (list1->val < list2->val) {
//			tail->next = list1;
//			tail = tail->next;
//			list1 = list1->next;
//		}
//		else {
//			tail->next = list2;
//			tail = tail->next;
//			list2 = list2->next;
//		}
//	}
//
//	if (list1)
//		tail->next = list1;
//	if (list2)
//		tail->next = list2;
//     
//	// 不能直接返回head，因为head此时是指向哨兵位而不是头节点
//	struct ListNode* del = head;
//	head = head->next;
//	free(del);
//
//	return head;
//}



////CM11 链表分割	https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
////现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，
////且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
//
////思路：创建两个链表并且带哨兵位，第一个链表都是小于等于x的节点，第二个是大于x的节点。并链接两个链表
////自己的实现
//ListNode* partition(ListNode* pHead, int x)
//{
//	// 思路：
//	// 小于x的尾插第一个链表
//	// 大于等于x的尾插第二个链表
//	ListNode* first_head = NULL;
//	ListNode* first_tail = NULL;
//
//	ListNode* second_head = NULL;
//	ListNode* second_tail = NULL;
//
//	// 创建两个链表的哨兵位
//	first_head = first_tail = (ListNode*)malloc(sizeof(ListNode));
//	second_head = second_tail = (ListNode*)malloc(sizeof(ListNode));
//	first_head->next = NULL;
//	second_head->next = NULL;
//
//	ListNode* tail = pHead;//原链表尾指针，用来遍历原链表
//
//	while (tail) {
//		if (tail->val < x) {
//			first_tail->next = tail;
//			first_tail = first_tail->next;
//		}
//		else {
//			second_tail->next = tail;
//			second_tail = second_tail->next;
//		}
//		tail = tail->next;
//	}
//
//	if (first_head->next == NULL || second_head->next == NULL)
//		return pHead;
//	else {
//		first_tail->next = second_head->next;
//		second_tail->next = NULL;
//		return first_head->next;
//	}
//}
//
////老师的实现
//ListNode* partition(ListNode* pHead, int x)
//{
//	ListNode* lesshead, * lesstail, * greaterhead, * greatertail;
//	lesshead = lesstail = (ListNode*)malloc(sizeof(ListNode));
//	greaterhead = greatertail = (ListNode*)malloc(sizeof(ListNode));
//
//	ListNode* cur = pHead;
//	while (cur) {
//		if (cur->val < x) {
//			lesstail->next = cur;
//			lesstail = lesstail->next;
//		}
//		else {
//			greatertail->next = cur;
//			greatertail = greatertail->next;
//		}
//		cur = cur->next;
//	}
//
//	//这里不需要判断第一链表和第二链表是否为空
//	//如果第一链表为空，那么第一链表的哨兵位指向了第二链表的头节点
//	//如果第二链表为空，那么第一链表尾结点的指针域指向第二链表的哨兵位的指针域，第二链表哨兵位的指针域为空
//	lesstail->next = greaterhead->next;
//	greatertail->next = NULL;
//	pHead = lesshead->next;
//
//	free(lesshead);
//	free(greaterhead);
//
//	return pHead;
//}



////OR36 链表的回文结构 https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
////对于一个链表，请设计一个时间复杂度为O(n), 额外空间复杂度为O(1)的算法，判断其是否为回文结构。
//
////思路：
////用快慢指针找到中间节点，偶数个链表中间节点为2/n+1。
////从中间节点开始向后的部分逆置
////然后一个指针从头节点开始，一个指针从中间节点开始比较
//
////版本一：手写找中间节点和反转链表
//bool chkPalindrome(ListNode* head) {
//	// 用快慢指针找到中间节点。
//	ListNode* fast = head;
//	ListNode* slow = head;
//	while (fast && fast->next) { //循环结束时，慢指针指向中间节点
//		fast = fast->next->next;
//		slow = slow->next;
//	}
//
//	// 从中间节点开始向后的部分逆置（逆置即三个指针迭代）
//	ListNode* n1 = NULL;
//	ListNode* n2 = slow;//n2指向第一个要逆置的节点，即中间节点
//	ListNode* n3 = n2->next;
//	while (n2) {
//		n2->next = n1;
//		// 迭代
//		n1 = n2;
//		n2 = n3;
//		if (n3)
//			n3 = n3->next;
//	}
//	// 迭代结束后，n1就是逆置后链表的头节点
//
//	// 然后从一个指针从头节点开始，一个指针从中间开始比较
//	while (n1) {
//		if (head->val != n1->val)
//			return false;
//
//		n1 = n1->next;
//		head = head->next;
//	}
//	return true;
//}
//
////版本二：直接调用找中间链表函数和反转链表函数
//struct ListNode* middleNode(struct ListNode* head) {
//	struct ListNode* slow = head;
//	struct ListNode* fast = head;
//
//	while (fast && fast->next) {
//		slow = slow->next;
//		fast = fast->next->next;
//	}
//	return slow;
//}
//
//struct ListNode* reverseList(struct ListNode* head) {
//	if (head == NULL)
//		return NULL;
//
//	struct ListNode* n0 = NULL;
//	struct ListNode* n1 = head;
//	struct ListNode* n2 = head->next;
//
//	while (n1) {
//		n1->next = n0;
//		// 迭代
//		n0 = n1;
//		n1 = n2;
//		if (n2)
//			n2 = n2->next;
//	}
//	return n0;
//}
//
//bool chkPalindrome(ListNode* head) {
//	ListNode* mid = middleNode(head);
//	ListNode* reverse_mid = reverseList(mid);
//
//	while (reverse_mid) {
//		if (head->val != reverse_mid->val)
//			return false;
//
//		reverse_mid = reverse_mid->next;
//		head = head->next;
//	}
//	return true;
//}



////160. 相交链表  https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
////给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
////版本一：暴力求解，A链表中每个节点和B链表中每个节点比较
//struct ListNode* getIntersectionNode(struct ListNode* headA,
//	struct ListNode* headB) {
//	struct ListNode* tailA = headA;
//	struct ListNode* tailB = headB;
//
//	while (tailA)
//	{
//		tailB = headB;
//		while (tailB)
//		{
//			if (tailA == tailB)
//				return tailA;
//			tailB = tailB->next;
//		}
//		tailA = tailA->next;
//	}
//	return NULL;
//}
//
////版本二：让pa和pb两个指针遍历A和B链表。
////思路：假设A链表相交之前的节点数是a，B链表相交之前的节点数是b，相交(含相交节点)之后的节点是c。
////那么pa指针遍历A和B链表走到相交节点的个数是a + c + b。pb指针遍历A和B链表走到相交节点的个数是b + c + a。节点数相等
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
//	if (headA == NULL || headB == NULL) {
//		return NULL;
//	}
//	struct ListNode* pA = headA, * pB = headB;
//	while (pA != pB) {
//		//将三目运算符的结果赋值给pA和pB
//		pA = pA == NULL ? headB : pA->next;//如果pA不为空那么继续向后遍历，如果为空从B链表开始向后遍历         
//		pB = pB == NULL ? headA : pB->next;//如果pB不为空那么继续向后遍历，如果为空从A链表开始向后遍历
//
//	}
//	return pA;
//}
//
////版本三：分别求出两个链表的长度LA和LB，长的先走差距步，在同时走，第一个相等的就是相交
////自己的实现
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
//	struct ListNode* tailA = headA;
//	struct ListNode* tailB = headB;
//
//	//求两个链表的长度LA和LB
//	int lenA = 1;
//	int lenB = 1;
//	while (tailA) {
//		tailA = tailA->next;
//		lenA++;
//	}
//
//	while (tailB) {
//		tailB = tailB->next;
//		lenB++;
//	}
//
//	if (tailA != tailB)//如果A和B链表最后的节点不相等，说明两个链表不相交
//		return NULL;
//
//	int lenAbs = (lenA > lenB) ? (lenA - lenB) : (lenB - lenA);
//	tailA = headA;
//	tailB = headB;
//
//	//长的先走差距步
//	// if (lenA > lenB) {
//	//     while (lenAbs--)
//	//         tailA = tailA->next;
//	// } else {
//	//     while (lenAbs--)
//	//         tailB = tailB->next;
//	// }
//	while (lenAbs--)
//	{
//		if (lenA > lenB)
//			tailA = tailA->next;
//		else
//			tailB = tailB->next;
//	}
//
//	//在同时走，第一个相等的就是相交
//	while (tailA != tailB) {
//		tailA = tailA->next;
//		tailB = tailB->next;
//	}
//	return tailA;
//}
//
////老师的实现
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
//	struct ListNode* tailA = headA;
//	struct ListNode* tailB = headB;
//
//	int lenA = 1;
//	int lenB = 1;
//	while (tailA) {
//		tailA = tailA->next;
//		lenA++;
//	}
//
//	while (tailB) {
//		tailB = tailB->next;
//		lenB++;
//	}
//
//	if (tailA != tailB)//如果A和B链表最后的节点不相等，说明两个链表不相交
//		return NULL;
//
//	int lenAbs = abs(lenA - lenB);
//	//假设A链表比B链表长，如果不是，修改长短指针
//	struct ListNode* longList = headA;
//	struct ListNode* shortList = headB;
//	if (lenA < lenB)
//	{
//		longList = headB;
//		shortList = headA;
//	}
//	while (lenAbs--)
//		longList = longList->next;
//
//	while (longList != shortList)
//	{
//		longList = longList->next;
//		shortList = shortList->next;
//	}
//	return longList;
//}



////141. 环形链表 给定一个链表，判断链表中是否有环 https://leetcode.cn/problems/linked-list-cycle/description/
////思路：
////用快慢两个指针通知从链表头节点开始向后走。慢指针一次走一步，快指针一次走两步。相遇说明有环
//bool hasCycle(struct ListNode* head) {
//	if (head == NULL)
//		return false;
//
//	struct ListNode* slow = head;
//	struct ListNode* fast = head;
//
//	while (fast->next) {
//		fast = fast->next->next;
//		slow = slow->next;
//
//		if (fast == NULL)
//			return false;
//		else if (fast == slow)
//			return true;
//	}
//	return false;
//}
//
//// 优化上方
//bool hasCycle(struct ListNode* head) {
//	struct ListNode* slow = head;
//	struct ListNode* fast = head;
//
//	// fast为空说明是空链表，fast->next为空说明是只有一个节点
//	// 这两种情况都不可能是环形链表
//	while (fast && fast->next) {
//		fast = fast->next->next;
//		slow = slow->next;
//		if (slow == fast) {
//			return true; // 如果相遇了，说明存在环
//		}
//	}
//
//	return false; // 如果能正常退出循环，说明不存在环
//}



////给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 NULL
////https://leetcode.cn/problems/linked-list-cycle-ii/description/
////思路：先用快慢指针确认是否为环形链表。
////如果是，那么其中一个指针从头开始，另一个从相遇点开始，同时一次走一步。再次相遇时就是环入口
//
////结论及解释：
////假设环外长度是a，环入口到环内相遇点的长度是b，相遇点到环入口的长度是c，n是圈数。
////1.慢指针一定在走完环内一周之前就会和快指针相遇，最慢也是刚好走完一周的情况。因为快慢指针在环内最长的距离就是一圈，并且快指针速度慢指针2倍，
////所以慢指针走完一圈时，快指针走完两周，此时相遇。慢指针走过的距离就是a+b。
////2.快指针在和慢指针相遇之前至少走完环内一圈。当快指针第一次经过相遇点时，慢指针肯定还没到此位置，
////所以一定是快指针至少第二次到相遇点时他们才会相遇。快指针走过的距离是a+b+n*(c+b)。
////3.无论何时停下（包括相遇时）快指针走过的长度是慢指针的2倍。因为快指针速度是慢指针2倍。2*(a+b)=a+b+n*(c+b)。
//struct ListNode* detectCycle(struct ListNode* head) {
//    struct ListNode* slow = head;
//    struct ListNode* fast = head;
//
//    while (fast && fast->next) { // 判断是否为环形链表
//        slow = slow->next;
//        fast = fast->next->next;
//        if (slow == fast) //如果是，停止循环
//            break;
//    }
//
//    //fast为空说明是空链表，fast->next为空说明是只有一个节点，都不可能是环形链表
//    if (fast == NULL || fast->next == NULL)
//        return NULL;
//
//    slow = head; //slow回到头
//    while (slow != fast) { //同时一次走一步，相等就是环入口
//        slow = slow->next;
//        fast = fast->next;
//    }
//    return fast;
//}



//随机链表的复制
//给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
//构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。
//新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。
//复制链表中的指针都不应指向原链表中的节点 。

//思路：
//1. 先复制每个节点再插入到对应节点后面，形成新链表，此时不管random指向，因为需要完成新链表后才能复制random。
//比如第二节点的random指向最后节点，此时新链表未完成，那么复制的节点的random就无法指向它应该指向的位置。
//2. 修改复制节点的random指向。复制节点的random指向是它对应节点的random的next（如果该位置为空就置为空）
//3. 将链表重新链接。把所有复制节点链接。
struct Node* copyRandomList(struct Node* head) {
    if (head == NULL)
        return NULL;
    
    //1.复制节点并插入到对应节点后
    for (struct Node* cur = head; cur != NULL; cur = cur->next->next)
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        copy->next = cur->next;
        cur->next = copy;
    }

    //2.调整复制节点的random指向
    for (struct Node* cur = head; cur != NULL; cur = cur->next->next)
    {
        struct Node* copy = cur->next;
        copy->random = (cur->random == NULL) ? NULL : cur->random->next;
    }

    //3.将复制节点链接
    struct Node* copyHead = head->next;
    for (struct Node* cur = head; cur != NULL; cur = cur->next)
    {
        struct Node* copy = cur->next;
        cur->next = copy->next;
        copy->next = (copy->next == NULL) ? NULL : copy->next->next;
    }
    return copyHead;
}